package com.xigua._高级数据结构或系统;

import java.util.*;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: ${todo}
 * @date 2022/4/1414:17
 */
public class _380_O1时间插入_删除和获取随机元素 {

    public static void main(String[] args) {
        RandomizedSet randomizedSet = new RandomizedSet();
        randomizedSet.insert(1);
        randomizedSet.remove(2);
        randomizedSet.insert(2);
        System.out.println(randomizedSet.getRandom());
        randomizedSet.remove(1);
        randomizedSet.insert(2);
        System.out.println(randomizedSet.getRandom());
    }



}

class RandomizedSet {

    List<Integer> nums;
    Map<Integer,Integer> map;
    Random random;
    public RandomizedSet() {
        nums = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        nums.add(val);
        map.put(val,nums.size()-1);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(index,last);
        map.put(last,index);
        map.remove(val);
        nums.remove(nums.size()-1);
        return true;
    }

    public int getRandom() {
        return nums.get(random.nextInt(nums.size()));
    }
}
